相亲结婚，数学教你找到最佳伴侣

成哇 2023-07-10

The following article is from 返朴 Author Pradeep Mutalik

点击上方蓝字“返朴”进入主页，可关注查阅往期文章

有情人终成眷属。当选择相亲来解决终生大事，我们能找到最理想的伴侣吗？相亲几次才能遇见那个TA？其实，这在数学上属于一类经典问题——最优停止理论。最神奇的在于，超越数e潜藏其中。为什么这个普适常数会出现你的相亲过程中，本文的谜题2将给出解答。谜题3则是另一个爱情延伸出来的数学问题（谜题1也很有意思）。祝大家情人节快乐！

撰文 | Pradeep Mutalik

编译 | 哪吒

上个月，我们给出三个谜题，它们看起来很平常，却包含了数的曲折故事。故事背后是神秘的超越数（欧拉数）e。我们最熟悉的就是它作为自然对数的底。e是一个普适常数，且有一个无限的小数表示：2.7 1828 1828 45 90 45…（这种间隔书写只是为了显示小数点后面15位数字的某种规律性）。那么，它为什么突然出现在我们的谜题中？

在回答这个问题以前，我们需要对e的性质有更多的了解。如同它的超越数兄弟π，e有无数多种表达方式，比如写成无穷级数的和，无限多个数的乘积，无限序列的极限，以及一个惊人的正则连分数等等。

我还记得第一次学习e的情景。那时我们在中学学习普通对数，我惊叹于如果把所有数表达为10的分数次方幂，它就能够将复杂的乘法转化为简单的加法。然而，我想知道，分数次幂与无理数幂是如何计算出来的？当然，计算整数次的方幂很容易，比如10²，10³，必要时，甚至可以通过求10⁵的平方根来计算10^2.5。但是，就像对数表那样，20就是10^1.30103，他们是如何得到的？如何从头开始构造一个完整的对数表呢? 我简直无法想象这是怎么做到的。

后来，我了解到一个神奇的公式可以实现这一壮举。它揭示了“自然对数”中“自然”的来源：

对于负指数，会出现交错项：

这个强大的公式可以用来计算e的任意实数次幂，包括从负无穷到正无穷的整数次幂或分数次幂，结果可以是想要的任意精确度。因而可以从头开始构造一个完整的自然对数表，再从这张表得到一般的对数。

令x=1，得到e的表达式：

另外，e具有许多惊人的性质，有一些包含在我们的谜题的解答中。但是有一条性质指出了e的本质，且使得对于对数以及指数增长和衰减的情形来说，e是很自然的：

这个公式表明e^x在所有点处的变化率就等于自身的值。如果表示时间，此式表明增长（或衰减，对于-x）的速率等于迄今为止积累的规模或数量。现实世界中有无数的现象在某个时间段内就是这样的，而且我们也知道它们是指数增长或衰减的例子。但是，除了实用性之外，e的这个属性中还有一种审美上表现出完美和自然的元素，能够真正激发人们的好奇心。它甚至带有道德教训；我喜欢把它想象成一个禅宗式的功能，在追求增长的过程中，它总是处于完美的平衡，永远不会超出或低于它所获得的。

警告：在下面的谜题解决方案中，我们将涉及比本谜题专栏中常见的更高级、看起来更可怕的数学。如果这些方程式让你目光呆滞，也不用担心；试着遵循一般的论点和概念。我希望每个人都能对我们的谜题有所了解，不管它是如何出现的，为什么会出现。在BBC的系列剧《人类的攀升》（The Ascent of Man）中，Jacob Bronowski在谈到John von Neumann的数学著作时说，阅读数学时遵循概念论证的调子是很重要的——方程式只是“低音部分的管弦乐”。

现在让我们试着找出e在谜题中是如何出现的。

谜题1：分解

问题a的解答：

在上篇中曾经给出提示：当每个等分的数值最接近e时，乘积达到最大值。更准确地说，当等分的数值处于e的两侧时，达到两个最大的乘积。对于我们这里考虑的比较小的、日常级别的数，当等分的数值与e相差最小的时候，可以取到乘积的最大值。

问题b的解答：

从上面可以很容易地看到，当两个相邻的等分的数值与e的距离几乎相等时，两个乘积将是最接近的，一个比e低，另一个比e高。（只有当函数围绕e对称时，这是严格正确的。这里它不是，但在这个范围内，它足够近，正如读者Michel Nizette出色地解释的那样。）

译者注

对函数求导，

当，即时，f(x)取得最大值。

由于e是无理数，当a为正整数时，前面的函数f(x)的最大值点不会是整数，这样当x取正整数时，f(x)的第一，第二大数值在处取得。

如果原始数是N，那么当比率N/e的小数部分接近0.5时，即当N/e接近两个整数的中点时，这种情况就会发生。因此，如果你构造一个N/e表，其中N从1到100，然后寻找最接近0.5的小数部分，你将得到所需的整数：53。53除以e得到19.4976，而将53分别19等分和20等分得到的乘积相差仅为0.0013%。

问题c的解答：

如同有些读者所解释的，答案涉及到一些基础的微积分知识，特别是对于一个函数，让其导数为零，找到其最大值。这里的函数是，等分的数值为。此函数的对数是，取它的最大值要简单一些。如果你能手动解决这个问题，那就恭喜你了! 但如果你对微积分不感兴趣，你可以直接在Wolfram Alpha^[1]中输入“”，得到，所以解为。因此最佳的等分值是。

瞧！这就是e如何出现并得到最大乘积的。

这告诉我们e具有最优化性质。它可以出现在找最大值或最小值的情形中，就像我们将在谜题2看到的那样。在计算函数的值时，其中x取遍所有正实数（这就是Steiner’s problem），可以看到e的这个性质的基础版本。在这无穷多个实数中，此函数取得最大值对应的x是e。函数x^1/x取最大值等价于函数Inx/x取最大值，而后者的导数是(1-Inx)/x²，此导数为零，当且仅当Inx=1，即x=e。

谜题2：相亲

正如读者所指出的，这是著名的秘书问题的重述。要点概述如下。

继承人必须根据以下规则从10个潜在的配偶候选人中选出最好的一个。候选人一个接一个地接受面试，在考虑下一个候选人之前，要么被接受（如果被认为是最好的），要么被拒绝。被拒绝的候选人不能被召回，一旦候选人被接受，流程就会停止。如果流程还没有结束，则在默认情况下必须接受最后一个候选对象。

问题a的解答：

a. 假设没有排名相同的情况，继承人如何最大限度地提高选择最佳伴侣的机会？

这种情况要求继承人无条件地拒绝特定数目的候选人（ “拒绝”阶段），然后进入“选择阶段”——在这个阶段中，继承人从剩余的候选人中选择第一个排名高于先前所有被拒绝的候选人。当拒绝阶段有一个特定的长度时，选择最佳候选人的机会是最大的。如果拒绝阶段较长（最好的候选人更有可能被拒绝）或较短（他没有足够的经验来对候选人进行适当的排名，导致接受排名较低的候选人），那么选择最佳的概率就会下降。

这被称为“最优停止”（optimal stopping）^[2]问题，e出现在其解中是因为它具有最优性。对于大量的候选人n，最初被拒绝的候选人数量应该等于n除以e。

这里是n = 10的概率计算，如果拒绝阶段(r) = 3，即拒绝3人，让我们来看看答案是多少。

首先，请注意，最佳候选人可能会在10次面试的任何时刻出现，有1/10的概率（1/n）处于任何特定的位置。对于每个面试者的位置(i)，我们将这个1/10乘以最佳候选人将在该位置被选中的概率。然后我们把所有位置的概率加起来，建立一般表达式。

• 如果最佳候选人处于1到3位，他们将被自动拒绝。选择到最佳候选人的概率：

• 如果最佳候选人处于第4位，他们将总被选择。此时的概率：

• 如果最佳候选人处于第5位，且先前排名最高的候选人在位置1到3，而不是位置4，则该最佳候选人将被选中。所以：

（译者注：3/4是因为“先前排名最高的候选人在位置1到3，而不是位置4”。）
• …
• 如果最佳候选人处于第10位（且先前排名最高的候选人在位置1到3，而不是其他位置），则

可以看到，在选择阶段的每个位置我们得到相同的表达式：，为了形式上的统一，在位置4的表达式可以写为。
在和式中提取公因子，找到最佳候选对象的概率为

当(r) = 4个初始候选对象被拒绝时，找到最佳候选对象的对应概率为39.8%。这是两个最高的值，如果最初拒绝的次数增加或减少，概率就会下降。这是否让你想起了分解谜题？这不是巧合，我们将在下面看到。
（译者注：，它两侧的整数是3与4，所以这里拒绝阶段(r) = 3或4。）
问题b的解答：
b. 如果有10%的概率两人并列第一，那么继承人遇见最佳伴侣的机会如何变化？
由于继承人现在有两个排名第一的候选人，找到最佳候选人的机会增加了。
问题c的解答：
c. 这是一个经典问题，其解与e有关。你能解释一下e是如何进入答案的吗？
e在这个谜题中两次进入场景! 当n变大时，欧拉数出现在做出最佳选择的概率中，以及最初拒绝人数的比例中。
我们上面推导的概率表达式可以表示为n→∞当时的极限，用x代入r/n（拒绝的比率），用p代替(i-1)/n（在每个n处的增量概率），用dp代替1/n（从一个整数到下一个整数的变化率）。
于是概率的极限为：

再次地，右边的表达式和我们在分解谜题中看到的相似。令其导数设为0，我们发现应该拒绝的候选对象的最优分数和做出最佳选择的概率都是1/e，约为36.8%。

译者注这里利用了微积分里面的“分割-近似-求和-取极限”的思想。

若记，定义在区间[x, 1]，把平均(n-r)等分，这样每个小区间的长度为，取，所以

概率的极限为：

问题d的解答：
d. 在这种更实际的选择场景中，继承人如何才能选到候选人的最高预期排名？
在上面的经典场景中，继承人采取了一种全有或全无的策略，即拒绝前几个候选人，然后选择第一个比所有被拒绝的候选人更好的候选人。虽然这确实最大化了找到最佳候选人的可能性，但如果最佳候选人在最初的落选者中，也可能导致他被一个排名较低的候选人所困。为了避免这种情况，他的最佳实用策略是一开始就非常挑剔，并寻找最好的候选人，然后随着候选人数量的减少，降低挑剔程度，选择那个基本满足“好”的候选人。
这个策略可以通过从只剩下最后一个候选人的情形开始往前分析来实现。这个人可以以相同的概率进入排名的任何位置。因此，他的排名的数学期望是所有人最终排名的平均值（在本例中为5.5，译者注：）。所以只要倒数第二个候选人的排名在前五名以内，就应该接受倒数第二的候选人，即使她可能不是绝对最好的。当剩下两名候选人时，对排名较高的候选人的数学期望将是3.67左右。
(译者注：)
所以对于倒数第三的候选人，只要她的排名在前三名以内，就应该选择她。通过精确计算，你可以大致确定在每个阶段需要挑剔的程度，这样有更多的机会得到一个非常好的候选者，而不是使用经典的算法。

谜题3：亲密无间
一个大礼堂正在上演一场只允许夫妇入场的演出。当一对夫妇进入礼堂时，他们随机挑选一对紧挨着的座位。每一对新婚夫妇都这样做，在很多情况下，这会导致夫妻之间有空座位。持续入场直到只剩下单个的座位，然后礼堂宣布满员，表演开始。
问题a的解答：
a. 当入座停止时，预计有多少比例的空座位？
答案是，随着座位数量的增加，空座位的比例接近，或约13.5%。
问题b的解答：
b. e是如何进入这个双人大礼堂的？
让我们看看当有少量按字母顺序标记的座位时会发生什么。将预期的空座位数量（译者注：空座位数量的数学期望）记为E₁、E₂、E₃、E₄，等等，其中下标是一排空席位的数量。
• 单个座位空着，一对夫妇不会占据着，所以E₁=1；
• 相邻的两个座位空着，则必有一对夫妇占据，所以E₂=0；
• 三个相邻的座位A、B、C空着，一对夫妇可能占据AB或BC。在任一情形，都只会留着一个座位，所以E₃=1；
• 四个相邻的座位ABCD空着, 一对夫妇可能占据BC，留下两个空座位；占据AB或CD，则不留下空座位。这给出了三种构型，总共有两个空座位，给出了平均期望。(译者注：)
通过探索接下来的几个数字之间的联系，有读者能够推导出递归关系，用E_n-2和E_n-1预测E_n（其中n≥2）：

得到序列：

这些数字除以席位数就得到了空缺席位的比例，有读者计算出10个席位的比例为16.24%，100个席位的比例为13.804%，1000个席位的比例为13.561%，6000个席位的比例为13.538%。你可以看到数字接近或13.5335…%。但是我们怎么知道这就是它们的目标呢？因为它们的关系需要很长时间才能计算出来。
递归关系虽然很好，但它就像试图一步一步地爬一个无限的楼梯。我们真正需要的是一个只依赖于n的封闭表达式。一个封闭表达式就像一台电梯。对任意n按下按钮，嗖! 电梯会带你到那里，甚至可以直达楼顶，那里的视野是无限的。
从递归关系中得到闭合公式（解析解）称为求解递归。这并没有什么灵丹妙药，虽然你可以尝试一些技巧，但这是一种艺术。Mathematica之类的数学程序就有这样的软件包。对于我们的问题，有读者给出了E_n的一个封闭表达式，表明E_n的极限就是。
所以e确实会进入剧院，但它是如何进入的呢?我们对此仍一无所知。它使用了何种超级力量？下面，我试着抽出问题的主要矛盾，也是其精华所在，而忽略其中错综复杂的代数。
首先，从E的序列得到两个差分序列：一阶差分序列D由E的相邻两个数值的差构成，二阶差分序列DD由D的相邻两个数值的差构成。从而D₁=E₁-E₀，D₂=E₂-E₁，D₃=E₃-E₂ 等等，和DD₁=D₁-D₀，DD₂=D₂-D₁，DD₃=D₃-D₂，以此类推(E₀, D₀均为0)。我将很快解释这样做的意义。下表列出了这三个序列的初始值。

通过对原始的递归关系进行一些复杂的代数运算，我们可以推导出DD_n的一个闭式表达式（解析解） (n≥1)：

通过与上表比较，我们可以验证该公式的正确性:

关键时刻来了：注意当你把所有DD加起来时会发生什么。

其他项都消掉了，只剩下D_n。这种求解递归式的方法被恰当地称为相消法 (telescoping)。
现在让我们把每个DD的解析表达式代回去。

看起来熟悉吗？将其与前面的e^-x无穷级数进行比较。事实上，对于很大的n，这就是e^-2或者的公式。
所以超越数的平方就神奇地出现在由空座位数量导出的一阶差分序列的分母中。它存在的原因是，这个过程需要对-2的连续正整数次幂除以相应的阶乘，然后求和，这正是e的幂的结构。
我们还有一些工作要做。通过类似的过程从D序列返回到E序列得到E_n。这个值除以n，就得到空座的比例。为了达到终点，我们需要做一些复杂的代数运算。就是说，e^-2仍然在最后的表达式中，它看起来是这样的：

当n→∞时，只剩下第一项，给出了我们前面已经找到的结果：。注意，对于读者列出的大而有限的数，仅仅前两项的和几乎完全符合未填充的分数的值。

注释

[1] Wolfram Alpha是一个智能计算工具，网址为ttps://www.wolframalpha.com/ [2] 可参考《最优停止理论 Optimal Stopping Theory 经典秘书问题 Classic Secretary Problem》 https://blog.csdn.net/hilda_Huang/article/details/8099202

本文译自Where Transcendental Numbers Hide in Everyday Math 原文链接：https://www.quantamagazine.org/why-eulers-number-is-just-the-best-20211124/